package codeRandomThoughts.Test98验证二叉搜索树;

import codeRandomThoughts.utils.TreeNode;

import java.util.TreeSet;

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return validBST(root).isBST;
    }

    public R validBST(TreeNode root) {
        //递归终止条件
        //遍历到叶子节点
        if (root.left == null && root.right == null) {
            return new R(true, root.val, root.val);
        }

        //本层做的事情
        //判断本层的三个节点是否满足二叉搜索树条件
        //默认升序排序
        TreeSet<Long> list = new TreeSet<>();
        list.add((long) root.val);
        if (root.left != null) {
            R left = validBST(root.left);
            if (!left.isBST || left.max >= root.val) {
                return new R(false);
            }
            list.add(left.max);
            list.add(left.min);
        }
        if (root.right != null) {
            R right = validBST(root.right);
            if (!right.isBST || right.min <= root.val) {
                return new R(false);
            }
            list.add(right.max);
            list.add(right.min);
        }
        Long minNum = list.first();
        Long maxNum = list.last();
        return new R(true, maxNum, minNum);
    }
}


class R {
    boolean isBST;
    long max;
    long min;

    public R(boolean isBST) {
        this.isBST = isBST;
    }

    public R() {
    }

    public R(boolean isBST, long max, long min) {
        this.isBST = isBST;
        this.max = max;
        this.min = min;
    }
}
